package com.jeff.question100;

import java.util.Stack;

/**
 * {@Description}
 *
 * <div> 在学校中，N个小朋友站成一队， 第i个小朋友的身高为height[i]，</div>
 * <div> 第i个小朋友可以看到的第一个比自己身高更高的小朋友j，那么j是i的好朋友(要求j &gt; i)。</div>
 * <div> 请重新生成一个列表，对应位置的输出是每个小朋友的好朋友位置，如果没有看到好朋友，请在该位置用0代替。</div>
 * <div> 小朋友人数范围是 [0, 40000]。</div>
 * {@Author} <b style="color:yellow">yaojianfeng</b> 2024/7/1 上午10:07
 */
import java.util.Stack;

public class FriendsFinder {
    public int[] findFriends(int[] heights) {
        int n = heights.length;
        int[] friends = new int[n];  // 默认值为0，表示没有找到好朋友
        Stack<Integer> stack = new Stack<>();  // 存储待匹配小朋友的位置

        for (int i = 0; i < n; i++) {
            // 遍历栈，检查栈顶小朋友是否可以成为当前小朋友的好朋友
            while (!stack.isEmpty() && heights[i] > heights[stack.peek()]) {
                // 当前小朋友可以成为栈顶小朋友的好朋友
                friends[stack.pop()] = i;
            }
            stack.push(i);  // 当前小朋友入栈，等待之后可能的匹配
        }

        return friends;
    }

    public static void main(String[] args) {
        FriendsFinder finder = new FriendsFinder();
        int[] heights = {5, 3, 6, 1, 2, 4};
        int[] result = finder.findFriends(heights);

        for (int i : result) {
            System.out.print(i + " ");
        }
    }
}

